#include<iostream>

//#include <cstddef>
//#include <cstdlib>
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        struct ListNode* lhead, * ltail, * ghead, * gtail;
//        lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));
//        ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
//        ltail->next = gtail->next = NULL;
//        struct ListNode* cur = pHead;
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                ltail->next = cur;
//                cur = cur->next;
//                ltail = ltail->next;
//            }
//            else
//            {
//                gtail->next = cur;
//                cur = cur->next;
//                gtail = gtail->next;
//            }
//        }
//        ltail->next = ghead->next;
//        gtail->next = NULL;
//        pHead = lhead->next;
//        free(lhead);
//        free(ghead);
//        return pHead;
//    }
//};


//#include <cstddef>
//class PalindromeList {
//public:
//    struct ListNode* find_mid(ListNode* head)
//    {
//        struct ListNode* slow, * fast;
//        slow = fast = head;
//        while (fast && fast->next)
//        {
//            slow = slow->next;
//            fast = fast->next;
//        }
//        return slow;
//    }
//
//    struct ListNode* reverse(ListNode* head)
//    {
//        if (head == NULL)
//            return NULL;
//        struct ListNode* prev, * cur, * Next;
//        cur = head;
//        Next = cur->next;
//        prev = NULL;
//        while (cur)
//        {
//            cur->next = prev;
//            prev = cur;
//            cur = Next;
//            if (Next)
//                Next = Next->next;
//        }
//        return prev;
//    }
//    bool chkPalindrome(ListNode* head) {
//        struct ListNode* mid = find_mid(head);
//        struct ListNode* rhead = reverse(mid);
//        while (head && rhead)
//        {
//            if (head->val != rhead->val)
//            {
//                return false;
//            }
//            else
//            {
//                head = head->next;
//                rhead = rhead->next;
//            }
//        }
//        return true;
//    }
//};

//
//bool hasCycle(struct ListNode* head) {
//    struct ListNode* fast, * slow;
//    fast = slow = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (slow == fast)
//            return true;
//    }
//    return false;
//}